• Interactive proofs and multi-prover verification frameworks unify probabilistic reasoning about correctness and soundness, spanning zero-knowledge, PCP-like verification, and efficient polylog-time checks across single- and multi-prover models [1], [14], [17], [16], [6], [8], [15].

• Circuit complexity and lower bounds emphasize proving limits of computation: depth-lower bounds, algebraic methods, parity/threshold circuits, PRAM bounds, and deterministic simulations of probabilistic circuits [2], [5], [19], [20], [18], [7].

• Pseudorandomness and derandomization showcase constructing pseudo-random generators, functions, and dispersers from weak assumptions to amplify reliability with limited randomness [3], [12], [13], [9], [20].

• Hardness of approximation and PCP-like verification explore how probabilistic verification frameworks bound approximability and enable robust membership verification, via PCP results and polylogarithmic-time checking [6], [8], [16], [1].